package com.wk.arth.dp;
/**
 * 你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多。买一本书需要27元。如何用最少的硬币组合正好付清，不需要对方找钱？
 * dp[x] = min(dp[x-2]+1,dp[x-5]+1,dp[x-7]+1)
 */
public class MinCoin {
	public int[] dp;
	public int count = 0;
	public MinCoin() {
		dp = new int[28];
		for (int i = 0; i < dp.length; i++) {
			dp[i] = -1;
		}
		dp[0] = 0;
	}

	//自顶向下
	public  int getDp(int x) {
		if(x<0) {
			return Integer.MAX_VALUE;
		}
		if(x == 0) {
			return dp[0];
		}
		if(dp[x]!=-1) {
			return dp[x];
		}
		count++;
		dp[x] = min(getDp(x-2), getDp(x-5),getDp(x-7));
		return dp[x];
	}
	// 自底向上
	public void newDp(int x) {
		dp[1] = Integer.MAX_VALUE;
		dp[2] = 1;
		dp[3] = Integer.MAX_VALUE;
		dp[4] = 2;
		dp[5] = 1;
		dp[6] = 3;
		dp[7] = 1;
		for (int i = 8; i < x+1; i++) {
			dp[i] = min(dp[i-2], dp[i-5], dp[i-7]);
		}
		System.out.println(dp[x]);
	}
	public void show(int x) {
		if(x<=0) {
			return;
		}
		int a = dp[x-2];
		int b = dp[x-5];
		int c = dp[x-7];
		int temp = Math.min(Math.min(a, b), c);

		if(temp == c) {
			System.out.print("7->");
			x = x-7;
			show(x);
			return;
		}
		if(temp == b) {
			System.out.print("5->");
			x = x-5;
			show(x);
			return;
		}
		if(temp == a) {
			System.out.print("2->");
			x = x-2;
			show(x);
			return;
		}
	
		
	}
	
	public int min(int x,int y,int z) {
		int t = Math.min(x, y);
		int t2 = Math.min(t, z);

		if(t2 == Integer.MAX_VALUE) {
			return t2;
		}
//		if(t2 == x) {
//			System.out.print("2->");
//		}
//		if(t2 == y) {
//			System.out.print("5->");
//		}
//		if(t2 == z) {
//			System.out.print("7->");
//		}
		return t2 + 1;
	}
	public static void main(String[] args) {
//		MinCoin minCoin = new MinCoin();
//		int num = minCoin.getDp(27);
//		minCoin.show(27);
//		System.out.println();
//		System.out.println(num);
//		System.out.println(minCoin.count);
		
		MinCoin minCoin2 = new MinCoin();
		minCoin2.newDp(27);
	}
}
